package com.dycong.common.leetcode.sort;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class QuickSort_II {

    public static void main(String[] args) {
        QuickSort_II quickSort_ii = new QuickSort_II();
//                int[] ints = new int[]{1, 2, 5, 8, 6, 5, 9, 5, 55, 5};
//        int[] ints = new int[]{0};
//        int[] ints = new int[]{-1,2,-8,-10};
//        int[] ints = new int[]{5, 2, 3, 1};
        int[] ints = new int[]{-74, 48, -20, 2, 10, -84, -5, -9, 11, -24, -91, 2, -71, 64, 63, 80, 28, -30, -58, -11, -44, -87, -22, 54, -74, -10, -55, -28, -46, 29, 10, 50, -72, 34, 26, 25, 8, 51, 13, 30, 35, -8, 50, 65, -6, 16, -2, 21, -78, 35, -13, 14, 23, -3, 26, -90, 86, 25, -56, 91, -13, 92, -25, 37, 57, -20, -69, 98, 95, 45, 47, 29, 86, -28, 73, -44, -46, 65, -84, -96, -24, -12, 72, -68, 93, 57, 92, 52, -45, -2, 85, -63, 56, 55, 12, -85, 77, -39};

        quickSort_ii.sortArray(ints);
        System.out.println(Arrays.toString(ints));
    }

    public List<Integer> sortArray(int[] nums) {
        sort(nums);

        List<Integer> res = new ArrayList<>();
        for (int i : nums) {
            res.add(i);
        }
        return res;
    }

    public void sort(int[] nums) {
        if (nums.length == 0 || nums.length == 1) {
            return;
        }
        sort(nums, 0, nums.length - 1);

    }

    public void sort(int[] nums, int left, int right) {
        if (left >= right) return;

        int pivotIndex = partition(nums, left, right);

        sort(nums, left, pivotIndex - 1);
        sort(nums, pivotIndex + 1, right);
    }

    public int partition(int[] nums, int left, int right) {
        int l = left;
        int r = right;
        int pivot = nums[l];

        for (; ; ) {
            //todo 因为nums[left] == pivot，所以l至少右移一位，pivot位置不会被动
            //todo 不超过本轮次右指针边界
            while (nums[l] <= pivot && l < right) {
                l++;
//                if (l == r) {
//                    break;
//                }
            }
            //todo 不超过本轮次左指针边界
            while (nums[r] > pivot && r > left) {
                r--;
//                if (l == r) {
//                    break;
//                }
            }

            if (r <= l) {
                break;
            }

            swap(nums, l, r);
        }

        //todo r是一个不满足nums[r] > pivot 所以可以作为 pivotIndex
        swap(nums, left, r);
        return r;
    }

    public void swap(int[] nums, int i, int j) {
        if (i == j) return;
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}
